#ifndef __DLIST_H
#define __DLIST_H

/* 该文件来源于Linux内核（include/linux/list.h）
 * 并经过修改去除了硬件预取链表项的功能。
 * 版权归属原作者所有。
 * Kulesh Shanmugasundaram (kulesh [squiggly] isis.poly.edu)
 */

/*
 * 简单的双向链表实现。
 *
 * 一些内部函数（"__xxx"）在操作整个链表时很有用，
 * 而不是单个条目，因为有时我们已经知道前一个/后一个条目，
 * 我们可以通过直接使用它们来生成更好的代码，
 * 而不是使用通用的单条目例程。
 */

/**
 * container_of - 将结构体的一个成员转换为包含该成员的完整结构体
 *
 * @ptr:    指向成员的指针。
 * @type:   包含该成员的容器结构体的类型。
 * @member: 结构体中成员的名称。
 */
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

#define container_of(ptr, type, member) ({          \
        const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
        (type *)( (char *)__mptr - offsetof(type,member) );})
/*
 * 这些是非空指针，在正常情况下会导致页面错误，
 * 用于验证没有人使用未初始化的链表条目。
 */
#define LIST_POISON1  ((void *) 0x00100100)
#define LIST_POISON2  ((void *) 0x00200)

// 标准链表节点（小结构体）
struct list_head
{
    struct list_head *prev;
    struct list_head *next;
};

#define LIST_HEAD_INIT(name) { &(name), &(name) }

#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)

// 宏定义语法规定只能有一条语句
// 如果需要多条语句，那就必须将多条语句放入一个do{}while(0)中使之成为一条复合语句
#define INIT_LIST_HEAD(ptr) \
    do { \
    (ptr)->next = (ptr); \
    (ptr)->prev = (ptr); \
} while (0)

/*
 * 在两个已知的连续条目之间插入一个新条目。
 *
 * 这仅用于我们已经知道前一个/后一个条目的内部链表操作！
 */
static inline void __list_add(struct list_head *new,
                struct list_head *prev,
                struct list_head *next)
{
    next->prev = new;
    new->next = next;
    new->prev = prev;
    prev->next = new;
}

/**
 * list_add - 添加一个新条目
 * @new:  要添加的新条目
 * @head: 在其后添加的链表头
 *
 * 在指定的头节点后插入一个新条目。
 * 这对于实现栈很有用。
 */
static inline void list_add(struct list_head *new, struct list_head *head)
{
    __list_add(new, head, head->next);
}

/**
 * list_add_tail - 添加一个新条目
 * @new:  要添加的新条目
 * @head: 在其前添加的链表头
 *
 * 在指定的头节点前插入一个新条目。
 * 这对于实现队列很有用。
 */
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
    __list_add(new, head->prev, head);
}

/*
 * 通过使前一个/后一个条目相互指向来删除一个链表条目。
 *
 * 这仅用于我们已经知道前一个/后一个条目的内部链表操作！
 */
static inline void __list_del(struct list_head *prev, struct list_head *next)
{
    next->prev = prev;
    prev->next = next;
}

/**
 * list_del - 从链表中删除条目。
 * @entry: 要从链表中删除的元素。
 * 注意：删除后，entry上的list_empty不会返回true，该条目处于未定义状态。
 */
static inline void list_del(struct list_head *entry)
{
    __list_del(entry->prev, entry->next);
    entry->next = (void *) 0;
    entry->prev = (void *) 0;
}

/**
 * list_del_init - 从链表中删除条目并重新初始化它。
 * @entry: 要从链表中删除的元素。
 */
static inline void list_del_init(struct list_head *entry)
{
    __list_del(entry->prev, entry->next);
    INIT_LIST_HEAD(entry);
}

/**
 * list_move - 从一个链表中删除并作为另一个链表的头节点添加
 * @list: 要移动的条目
 * @head: 将在我们的条目前面的头节点
 */
static inline void list_move(struct list_head *list,
                struct list_head *head)
{
    __list_del(list->prev, list->next);
    list_add(list, head);
}

/**
 * list_move_tail - 从一个链表中删除并作为另一个链表的尾节点添加
 * @list: 要移动的条目
 * @head: 将在我们的条目后面的头节点
 */
static inline void list_move_tail(struct list_head *list,
                    struct list_head *head)
{
    __list_del(list->prev, list->next);
    list_add_tail(list, head);
}

/**
 * list_empty - 测试链表是否为空
 * @head: 要测试的链表。
 */
static inline int list_empty(struct list_head *head)
{
    return head->next == head;
}

static inline void __list_splice(struct list_head *list,
                    struct list_head *head)
{
    struct list_head *first = list->next;
    struct list_head *last = list->prev;
    struct list_head *at = head->next;

    first->prev = head;
    head->next = first;

    last->next = at;
    at->prev = last;
}

/**
 * list_splice - 连接两个链表
 * @list: 要添加的新链表。
 * @head: 在第一个链表中添加的位置。
 */
static inline void list_splice(struct list_head *list, struct list_head *head)
{
if (!list_empty(list))
__list_splice(list, head);
}

/**
 * list_splice_init - 连接两个链表并重新初始化被清空的链表。
 * @list: 要添加的新链表。
 * @head: 在第一个链表中添加的位置。
 *
 * @list处的链表将被重新初始化
 */
static inline void list_splice_init(struct list_head *list,
struct list_head *head)
{
if (!list_empty(list)) {
__list_splice(list, head);
INIT_LIST_HEAD(list);
}
}

/**
 * list_entry - 获取此条目的结构体
 * @ptr:    &struct list_head指针。
 * @type:   包含该结构体的类型。
 * @member: 结构体中list_struct的名称。
 */
#define list_entry(ptr, type, member) \
((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))

/**
 * list_for_each    -    遍历链表
 * @pos:    用作循环计数器的&struct list_head。
 * @head:   链表的头节点。
 */
#define list_for_each(pos, head) \
for (pos = (head)->next; pos != (head); \
pos = pos->next)
/**
 * list_for_each_prev    -    反向遍历链表
 * @pos:    用作循环计数器的&struct list_head。
 * @head:   链表的头节点。
 */
#define list_for_each_prev(pos, head) \
for (pos = (head)->prev; pos != (head); \
pos = pos->prev)

/**
 * list_for_each_safe    -    安全地遍历链表，防止链表条目被删除
 * @pos:    用作循环计数器的&struct list_head。
 * @n:      用作临时存储的另一个&struct list_head
 * @head:   链表的头节点。
 */
#define list_for_each_safe(pos, n, head) \
for (pos = (head)->next, n = pos->next; pos != (head); \
pos = n, n = pos->next)

/**
 * list_for_each_entry    -    遍历给定类型的链表
 * @pos:    用作循环计数器的类型指针。
 * @head:   链表的头节点。
 * @member: 结构体中list_struct的名称。
 */
#define list_for_each_entry(pos, head, member)                \
for (pos = list_entry((head)->next, typeof(*pos), member);    \
&pos->member != (head);                     \
pos = list_entry(pos->member.next, typeof(*pos), member))

/**
 * list_for_each_entry_safe - 安全地遍历给定类型的链表，防止链表条目被删除
 * @pos:    用作循环计数器的类型指针。
 * @n:      用作临时存储的另一个类型指针
 * @head:   链表的头节点。
 * @member: 结构体中list_struct的名称。
 */
#define list_for_each_entry_safe(pos, n, head, member)            \
for (pos = list_entry((head)->next, typeof(*pos), member),    \
n = list_entry(pos->member.next, typeof(*pos), member);    \
&pos->member != (head);                     \
pos = n, n = list_entry(n->member.next, typeof(*n), member))

#endif